Email: mitalib at cs dot washington dot edu
Office: Gates Center 211
About
I am a theoretical computer scientist and an Assistant Professor in the Allen School of Computer Science & Engineering at the University of Washington. My research explores complexity theory and algorithms and I am particularly interested in approximation algorithms, probabilistically checkable proofs, and high-dimensional expanders.
I received my undergrad degree from IIT Madras and my Ph.D. in Computer Science from Harvard University in 2022, advised by Prof. Madhu Sudan. After that, I was a postdoc at CMU, hosted by Professors Aayush Jain and Pravesh Kothari, followed by a postdoc in the MIT Department of Mathematics.
I will be recruiting Ph.D. students for the December 2025 application cycle. If you’re interested in working with me, please apply to the UW’s CS Ph.D. program and list my name on your application.
Publications
-
Quasi-Linear Size PCPs with Small Soundness from HDX.
with Dor Minzer and Nikhil Vyas (Appendix D by Zhiwei Yun)
STOC 2025 (Best Paper Award) -
Rounding Large Independent Sets on Expanders.
with Tim Hsieh and Pravesh Kothari
STOC 2025 -
Constant Degree Networks for Almost-Everywhere Reliable Transmission.
with Dor Minzer
STOC 2025 -
Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity.
with Karthik C. S. and Dor Minzer
STOC 2025 -
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures.
with Prashanti Anderson, Rares-Darius Buhai, Pravesh Kothari and David Steurer -
Constant Degree Direct Product Testers with Small Soundness.
with Noam Lifshitz and Dor Minzer
FOCS 2024 -
Characterizing Direct Product Testing via Coboundary Expansion.
with Dor Minzer
STOC 2024 -
Solving Unique Games over Globally Hypercontractive Graphs.
with Dor Minzer
CCC 2024 -
Polynomial-Time Power-Sum Decomposition of Polynomials.
with Tim Hsieh, Pravesh Kothari and Jeff Xu
FOCS 2022 -
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.
with Max Hopkins, Tali Kaufman and Shachar Lovett
STOC 2022 -
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.
with Max Hopkins, Tali Kaufman and Shachar Lovett
SODA 2022 -
Playing Unique Games on Certified Small-Set Expanders.
with Boaz Barak, Pravesh Kothari, Tselil Schramm and David Steurer
STOC 2021 -
Optimal Fine-grained Hardness of Approximation of Linear Equations.
with Nikhil Vyas
ICALP 2021 -
Local decoding and testing of polynomials over grids.
with Srikanth Srinivasan and Madhu Sudan
Random Structures and Algorithms (Journal) -
Imperfect Gaps in Gap-ETH and PCPs.
with Nikhil Vyas
CCC 2019 -
Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.
with Jack Murtagh and Nikhil Vyas
NeurIPS 2018 -
The Price of Selection in Differential Privacy.
with Jonathan Ullman
COLT 2017 -
On the Sensitivity Conjecture for Read-k Formulas.
with Satyanarayana V. Lokam, Sébastien Tavenas and Ameya Velingker
MFCS 2016
Expositions
-
Elementary analysis of isolated zeroes of a polynomial system.
with Madhu Sudan, Santhoshini Velusamy and David Xiang -
An Exposition of Dinur-Khot-Kindler-Minzer-Safra’s Proof for the 2-to-2 Games Conjecture.
with Chi-Ning Chou and Zhao Song
Teaching
- Fall 2025: CSE 431 - Undergrad Complexity Theory, UW
- Spring 2025: 18.200 - Principles of Discrete Math, MIT (Recitation Leader, Instructor: Peter Shor)
- Fall 2024: 18.424 - Undergraduate Seminar in Information Theory, MIT
- Spring 2024: 18.200 - Principles of Discrete Math, MIT (Recitation Leader, Instructors: Peter Shor & Ankur Moitra)
- Fall 2023: 18.01 - Single Variable Calculus, MIT (Recitation Leader, Instructor: Prof. Larry Guth)
- Spring 2019: CS229r - Information Theory in Computer Science, Harvard (TA, Instructor: Prof. Madhu Sudan)
Service
- PC Member: STOC 2025
- Co-organized HDX Workshop at STOC 2025 (with Max Hopkins, Yotam Dikstein & Dor Minzer)